package com.zk.algorithm.tree;

import com.zk.algorithm.Utils;
import com.zk.algorithm.annotation.Hard;
import com.zk.algorithm.annotation.LeetCode;
import com.zk.algorithm.bean.TreeNode;
import com.zk.algorithm.factory.TreeFactory;

/**
 * @author zk
 */
@Hard
@LeetCode("124")
public class BinaryTreeMaximumPathSum {

    public static void main(String...args) {
//        System.out.println(new BinaryTreeMaximumPathSum().maxPathSum(TreeFactory.buildTree(new Integer[]{
//                -10, 9, 20, null, null, 15, 7
//        })));
//
//        System.out.println(new BinaryTreeMaximumPathSum().maxPathSum(TreeFactory.buildTree(new Integer[]{
//                -3
//        })));
//
//        System.out.println(new BinaryTreeMaximumPathSum().maxPathSum(TreeFactory.buildTree(new Integer[]{
//                1, 2
//        })));
//
//        System.out.println(new BinaryTreeMaximumPathSum().maxPathSum(TreeFactory.buildTree(new Integer[]{
//                2, -1
//        })));
//
//        System.out.println(new BinaryTreeMaximumPathSum().maxPathSum(TreeFactory.buildTree(new Integer[]{
//                1, -2, 3
//        })));

        System.out.println(new BinaryTreeMaximumPathSum().maxPathSum(TreeFactory.buildTree(new Integer[]{
                1,-2,-3,1,3,-2,null,-1
        })));
    }

    /**
     * 50 / 93 test cases passed.
     *
     * [1,-2,-3,1,3,-2,null,-1]
     * Output: 4
     * Expected: 3
     *
     * @param root
     * @return
     */
    public int maxPathSum(TreeNode root) {
        if (root == null) {
            return Integer.MIN_VALUE;
        }

        int rootMaxSum = root.val;
        int leftMaxSum = maxPathSum(root.left);
        int rightMaxSum = maxPathSum(root.right);
        int rootTreeMaxSum = getRootTreeMaxSum(root, leftMaxSum, rightMaxSum);
        int rootLeftTreeMaxSum = getParentChildMaxSum(root, leftMaxSum);
        int rootRightTreeMaxSum = getParentChildMaxSum(root, rightMaxSum);

        return Utils.max(rootMaxSum, rootTreeMaxSum, leftMaxSum, rightMaxSum, rootLeftTreeMaxSum, rootRightTreeMaxSum);
    }

    private int getParentChildMaxSum(TreeNode root, int childSum) {
        int rootVal = root.val;

        if (childSum != Integer.MIN_VALUE) {
            rootVal += childSum;
        }

        return rootVal;
    }

    private int getRootTreeMaxSum(TreeNode root, int leftMaxSum, int rightMaxSum) {
        int rootMaxSum = root.val;

        if (leftMaxSum != Integer.MIN_VALUE) {
            rootMaxSum += leftMaxSum;
        }

        if (rightMaxSum != Integer.MIN_VALUE) {
            rootMaxSum += rightMaxSum;
        }

        return rootMaxSum;
    }

}
